// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-25 11:20
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.FindDuplicates;

import java.util.ArrayList;
import java.util.List;

public class FindDuplicates {
    public List<Integer> findDuplicates(int[] nums) {
        // 原地进行Hash，使用原来的空间记录信息
        ArrayList<Integer> res = new ArrayList<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            nums[(nums[i] - 1) % len] += len;// 如果当前位置的值出现过两次，数值会大于2n
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] >= 2 * len) {
                res.add(i+1);
            }
        }
        return res;
    }
}
